package cg.studio.practise;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.junit.Test;

public class Shuffle
{
  @Test
  public void testShuffle()
  {
    testShuffle( "aaaaa".toCharArray() );
    testShuffle( "aaabb".toCharArray() );
    testShuffle( "aaaccccccaabb".toCharArray() );
  }
  
  public void testShuffle( char[] str )
  {
    System.out.println( "Origin Str:   " + new String( str ) );
    boolean can = fancyShuffleViaMap( str );
    if( !can )
    {
      System.out.println( "can NOT shuffle." );
    }
    else
      System.out.println( "shuffled Str: " + new String( str ) );
  }
  
  /**
   * Write a function 
   * bool fancy_shuffle(char* str); 
   * which rearranges characters in the string given as input, 
   * in such a way that no same character occurs twice in a row (that is, next to each other). 
   * If such rearrangement is not possible, the function should return false.
   * 
   * solution 1: go through the <str>, generate a map from (char==>count). 
   * if the max count > (total_count+1)/2, return false 
   * Then, start with the char with the max count to the min count, put the char in the array in the even place, 
   * until to the end.
   * then put chars into odd place.
   * For sample: a=>5, b=>4, c=>4, 
   * a a a a a ==> a a a a a b b ==> ababa a a b b ==> ababacacacbcb
   */
  public static boolean fancyShuffleViaMap( char[] str )
  {
    final Map< Character, Integer > charCountMap = new HashMap< Character, Integer >();
    //generate the map
    for( char theChar : str )
    {
      Integer count = charCountMap.get( theChar );
      if( count == null )
      {
        count = 1;
      }
      else
      {
        count++;
      }
      charCountMap.put( theChar, count );
    }
    
    //sort by count
    Set<Character> charSet = charCountMap.keySet();
    List<Character> charList = new ArrayList<Character>( charSet );
    //sort descending order
    Collections.sort( charList, 
                      new Comparator<Character>()
                      {
                        public int compare( Character c1, Character c2 )
                        {
                          return charCountMap.get( c2 ) - charCountMap.get( c1 );
                        }
                      });
    
    Iterator<Character> iter = charList.iterator();
    char curChar = iter.next();
    int count = charCountMap.get( curChar );
    if( count > (str.length+1)/2 )
      return false;

    //put even first
    for( int i=0; i<str.length; i+=2 )
    {
      if( count == 0 )
      {
        curChar = iter.next();
        count = charCountMap.get( curChar );
      }
      str[i] = curChar;
      --count;
    }
    for( int i=1; i<str.length; i+=2 )
    {
      if( count == 0 )
      {
        curChar = iter.next();
        count = charCountMap.get( curChar );
      }
      str[i] = curChar;
      --count;
    }
    
    return true;
  }
}
